/*-*
 * FILENAME  :
 *    $HeadURL$
 *
 * STATUS  :
 *    $Revision$
 *
 *    $Author$
 *    $Date$
 *  
 *    
 * Copyright (c) 2011 Gonalge Ltda. All rights reserved.
 *
 ****************************************************************/

package org.gonalge.arbolrojonegro.negocio;

import org.gonalge.arbolrojonegro.dto.Nodo;
import org.gonalge.arbolrojonegro.type.CasoArbol;
import org.gonalge.arbolrojonegro.type.ColorNodo;

/**
 * 
 * @author Geremias Gonzalez
 */
public class ArbolRojoNegro {

    private Nodo raiz = null;

    private Nodo raizAux;

    private final Lista lista = new Lista();

    private final Lista historialList = new Lista();

    private final Lista pasosActualList = new Lista();

    private final Lista recorridoList = new Lista();

    private final Lista arbolList = new Lista();

    private int nivelRecorrido;

    private String rojo = "";

    private String casos;

    private boolean insertar;

    private final Archivo archivo = new Archivo();

    private int elemento = 0;

    public boolean esHoja(Nodo r) {
        return (r != null && r.getRD() == null && r.getRI() == null);

    }

    public void insertar(int ele) {
        elemento = ele;
        rojo = "no";
        casos = "";
        arbolList.setSize(0);
        raizAux = actualizar(raiz);
        arbolList.insertar(arbolList.getSize(), actualizar(raiz));
        insertar = false;
        recorridoList.setSize(0);
        raiz = insertarR(actualizar(raiz), ele);
        raiz.setColor(ColorNodo.NEGRO);
        arbolList.insertar(arbolList.getSize(), actualizar(raiz));
        while (rojo == "si") {
            rojo = "no";
            insertar = true;
            raiz = actualizar(raiz);
            raiz = insertarR(raiz, ele);
            raiz.setColor(ColorNodo.NEGRO);
            arbolList.insertar(arbolList.getSize(), actualizar(raiz));
        }
        lista.insertar(lista.getSize(), actualizar(raiz));
        historialList.insertar(historialList.getSize(), "******* Historial de la insercion del elemento " + (Object) Integer.toString(ele) + " : *******");
    }

    private Nodo insertarR(Nodo r, int e) {
        if (r == null) {
            r = new Nodo();
            r.setEle(e);
            r.setColor(ColorNodo.ROJO);
            nivelRecorrido = 1;
        } else {
            if (r.getEle() < e) {
                if (!insertar)
                    recorridoList.insertar(recorridoList.getSize(), r);
                r.setRD(insertarR(r.getRD(), e));
                nivelRecorrido++;
                if (nivelRecorrido >= 3) {
                    if (existeRojoRojo(r)) {
                        rojo = "si";
                        if (insertar) {
                            arbolList.insertar(arbolList.getSize(), actualizar(r));
                            insertar = false;
                            CasoArbol casoArbol = (r.getRI() != null) ? (r.getRI().getColor() == ColorNodo.ROJO) ? CasoArbol.CASO_DOS : CasoArbol.CASO_UNO : CasoArbol.CASO_UNO;
                            casos = casos + casoArbol.getId();
                            switch (casoArbol) {
                                case CASO_UNO:
                                    r = formaUno(r, e);
                                    break;
                                case CASO_DOS:
                                    r = formaDos(r);
                                    break;
                            }
                            arbolList.insertar(arbolList.getSize(), actualizar(r));
                        }
                    }
                }
            }
            if (r.getEle() > e) {
                if (!insertar)
                    recorridoList.insertar(recorridoList.getSize(), r);
                r.setRI(insertarR(r.getRI(), e));
                nivelRecorrido++;
                if (nivelRecorrido >= 3) {
                    if (existeRojoRojo(r)) {
                        rojo = "si";
                        if (insertar) {
                            arbolList.insertar(arbolList.getSize(), actualizar(r));
                            insertar = false;
                            CasoArbol casoArbol = (r.getRD() != null) ? (r.getRD().getColor() == ColorNodo.ROJO) ? CasoArbol.CASO_DOS : CasoArbol.CASO_UNO : CasoArbol.CASO_UNO;
                            casos = casos + casoArbol.getId();
                            switch (casoArbol) {
                                case CASO_UNO:
                                    r = formaUno(r, e);
                                    break;
                                case CASO_DOS:
                                    r = formaDos(r);
                                    break;
                            }
                            arbolList.insertar(arbolList.getSize(), actualizar(r));
                        }
                    }
                }
            }
        }
        return r;
    }

    private Nodo insertarAB(Nodo r, Nodo e, int x, int y, int a) {
        if (r == null) {
            r = new Nodo();
            r.setColor(e.getColor());
            r.setEle(e.getEle());
            r.setX(x);
            r.setY(y);
        } else {
            if (r.getEle() < e.getEle()) {
                r.setRD(insertarAB(r.getRD(), e, r.getX() + a, r.getY() + 50, a - (a / 2) + 5));
            }
            if (r.getEle() > e.getEle()) {
                r.setRI(insertarAB(r.getRI(), e, r.getX() - a, r.getY() + 50, a - (a / 2) + 5));
            }
        }
        return r;
    }

    private boolean existeRojoRojo(Nodo r) {
        if (colorNodo(r.getRD()) == ColorNodo.ROJO) {
            if (colorNodo(r.getRD().getRD()) == ColorNodo.ROJO)
                return true;
            if (colorNodo(r.getRD().getRI()) == ColorNodo.ROJO)
                return true;
        }
        if (colorNodo(r.getRI()) == ColorNodo.ROJO) {
            if (colorNodo(r.getRI().getRD()) == ColorNodo.ROJO)
                return true;
            if (colorNodo(r.getRI().getRI()) == ColorNodo.ROJO)
                return true;
        }
        return false;
    }

    private ColorNodo colorNodo(Nodo r) {
        if (r != null)
            return r.getColor();
        return ColorNodo.NEGRO;
    }

    private Nodo formaUno(Nodo r, int e) {
        CasoArbol casoArbol = null;
        if (r.getRD() != null) {
            if (r.getEle() < e)
                casoArbol = (r.getRD().getRD() != null) ? CasoArbol.CASO_UNO : CasoArbol.CASO_DOS;
            else
                casoArbol = (r.getRI().getRD() != null) ? CasoArbol.CASO_CUATRO : CasoArbol.CASO_TRES;
        } else
            casoArbol = (r.getRI().getRD() != null) ? CasoArbol.CASO_CUATRO : CasoArbol.CASO_TRES;

        casos = casos + casoArbol.getId();
        switch (casoArbol) {
            case CASO_UNO:
                r = rotarIzquierda(r);
                break;
            case CASO_DOS:
                r.setRD(rotarDerecha(r.getRD()));
                r = rotarIzquierda(r);
                break;
            case CASO_TRES:
                r = rotarDerecha(r);
                break;
            case CASO_CUATRO:
                r.setRI(rotarIzquierda(r.getRI()));
                r = rotarDerecha(r);
                break;
        }
        r.setColor(ColorNodo.NEGRO);
        r.getRD().setColor(ColorNodo.ROJO);
        r.getRI().setColor(ColorNodo.ROJO);
        return r;
    }

    private Nodo rotarIzquierda(Nodo r) {
        Nodo B = r.getRD();
        r.setRD(B.getRI());
        B.setRI(r);
        return B;
    }

    private Nodo rotarDerecha(Nodo r) {
        Nodo B = r.getRI();
        r.setRI(B.getRD());
        B.setRD(r);
        return B;
    }

    public Nodo formaDos(Nodo r) {
        if (r.getEle() != raiz.getEle())
            r.setColor(ColorNodo.ROJO);
        else
            r.setColor(ColorNodo.NEGRO);

        if (r.getRD() != null)
            r.getRD().setColor(ColorNodo.NEGRO);
        if (r.getRI() != null)
            r.getRI().setColor(ColorNodo.NEGRO);
        return r;
    }

    public Nodo actualizar(Nodo r) {
        int a = altura(r);
        a = (a < 4) ? 60 : a * 35;
        Lista li = preOrden(r);
        r = null;
        for (int i = 0; i < li.getSize(); i++) {
            r = insertarAB(r, (Nodo) li.consultar(i), 700, 100, a);
        }
        return r;
    }

    public void preOrden(Nodo r, Lista l) {
        if (r != null) {
            l.insertar(l.getSize(), r);
            preOrden(r.getRI(), l);
            preOrden(r.getRD(), l);
        }
    }

    public Lista preOrden(Nodo r) {
        Lista li = new Lista();
        preOrden(r, li);
        return li;
    }

    public Lista preOrden() {
        Lista li = new Lista();
        preOrden(raiz, li);
        return li;
    }

    public int altura(Nodo r) {
        int h1 = 0, h2 = 0;
        if (r != null) {
            h1++;
            if (r.getRD() != null)
                h1 = altura(r.getRD()) + 1;
            if (r.getRI() != null)
                h2 = altura(r.getRI()) + 1;
        }
        return h1 > h2 ? h1 : h2;
    }

    public int Altura() {
        return altura(raiz);
    }

    public void cargarcaLHistrial() {

        for (int i = 0; i < recorridoList.getSize(); i++) {
            Nodo a = (Nodo) recorridoList.consultar(i);
            historialList.insertar(historialList.getSize(), archivo.enLiteral(elemento, a.getEle()));
        }

        int i = 0;
        while (i < casos.length()) {
            int e = Integer.parseInt(casos.charAt(i) + "");
            String s;
            if (e == 1) {
                int e1 = Integer.parseInt(casos.charAt(i + 1) + "");
                s = archivo.forma(e, e1);
                i++;
            } else
                s = archivo.forma(e, 0);
            i++;
            historialList.insertar(historialList.getSize(), s);
        }
    }

    public void cargarcaLPasosA() {
        pasosActualList.setSize(0);
        for (int i = 0; i < recorridoList.getSize(); i++) {
            Nodo a = (Nodo) recorridoList.consultar(i);
            pasosActualList.insertar(pasosActualList.getSize(), archivo.enLiteral(elemento, a.getEle()));
        }

        int i = 0;
        while (i < casos.length()) {
            int e = Integer.parseInt(casos.charAt(i) + "");
            String s;
            if (e == 1) {
                int e1 = Integer.parseInt(casos.charAt(i + 1) + "");
                s = archivo.forma(e, e1);
                i++;
            } else
                s = archivo.forma(e, 0);
            i++;
            pasosActualList.insertar(pasosActualList.getSize(), s);
        }

    }

    public boolean existe(int e) {
        return existeEle(raiz, e);
    }

    private boolean existeEle(Nodo R, int ele) {// ***
        if (R != null) {
            if (R.getEle() == ele)
                return true;
            else {
                if (ele > R.getEle())
                    return existeEle(R.getRD(), ele);
                else
                    return existeEle(R.getRI(), ele);
            }
        } else
            return false;
    }

    public int nivel(int e) {
        return nivel(raiz, e);
    }

    private int nivel(Nodo R, int ele) {// ***
        if (R != null) {
            if (R.getEle() == ele)
                return 0;
            else {
                if (ele > R.getEle())
                    return nivel(R.getRD(), ele) + 1;
                else
                    return nivel(R.getRI(), ele) + 1;
            }
        } else
            return -10;
    }

    private void inOrden(Nodo r, Lista l) {
        if (r != null) {
            inOrden(r.getRI(), l);
            l.insertar(l.getSize(), r);
            inOrden(r.getRD(), l);
        }
    }

    public Lista inOrden() {
        Lista li = new Lista();
        inOrden(raiz, li);
        return li;
    }

    private void posOrden(Nodo r, Lista l) {
        if (r != null) {
            posOrden(r.getRI(), l);
            posOrden(r.getRD(), l);
            l.insertar(l.getSize(), r);
        }
    }

    public Lista posOrden() {
        Lista li = new Lista();
        posOrden(raiz, li);
        return li;
    }

    private void listaHojas(Nodo r, Lista l) {
        if (r != null) {
            listaHojas(r.getRI(), l);
            listaHojas(r.getRD(), l);
            if (esHoja(r))
                l.insertar(l.getSize(), r);

        }
    }

    public Lista listaHojas() {
        Lista li = new Lista();
        listaHojas(raiz, li);
        return li;
    }

    private int nodosExternos(Nodo r) {

        if (r == null) {
            return 1;
        } else {
            return nodosExternos(r.getRI()) + nodosExternos(r.getRD());
        }
    }

    public int nodosExternos() {
        return nodosExternos(raiz);

    }

    private int peso(Nodo r) {
        if (r == null) {
            return 0;
        } else {
            return peso(r.getRD()) + peso(r.getRI()) + 1;
        }
    }

    public int peso() {
        return peso(raiz);
    }

    private int cantidadRojo(Nodo r) {
        if (r != null) {
            if (r.getColor() == ColorNodo.ROJO)
                return cantidadRojo(r.getRD()) + cantidadRojo(r.getRI()) + 1;
            else
                return cantidadRojo(r.getRD()) + cantidadRojo(r.getRI());
        } else
            return 0;

    }

    public int cantidadRojo() {
        return cantidadRojo(raiz);
    }

    public boolean tieneunHijo(Nodo r) {
        return (r.getRD() != null && r.getRI() == null) || (r.getRD() == null && r.getRI() != null);
    }

    public boolean tienedosHijo(Nodo r) {
        return (r.getRD() != null && r.getRI() != null);
    }

    private int cantidadPadre(Nodo r) {
        if (r != null) {
            if (tienedosHijo(r) || tieneunHijo(r))
                return cantidadPadre(r.getRD()) + cantidadPadre(r.getRI()) + 1;
            else
                return cantidadPadre(r.getRD()) + cantidadPadre(r.getRI());
        } else
            return 0;

    }

    public int cantidadPadre() {
        return cantidadPadre(raiz);
    }

    public Nodo getRaiz() {
        return raiz;
    }

    public void setRaiz(Nodo raiz) {
        this.raiz = raiz;
    }

    public Nodo getRaizAux() {
        return raizAux;
    }

    public Lista getLista() {
        return lista;
    }

    public Lista getHistorialList() {
        return historialList;
    }

    public Lista getPasosActualList() {
        return pasosActualList;
    }

    public Lista getRecorridoList() {
        return recorridoList;
    }

    public Lista getArbolList() {
        return arbolList;
    }

    public String getCasos() {
        return casos;
    }

}
